#include "util.h"
#include "common_sort.h"
#include <algorithm>

/*
T(n) = O(n+k), n is the number of elements in input array and k is the range of input
Auxiliary Space: O(n+k)

Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted

keys as index in counting sort
*/

void CountingSort::sort(std::vector<int>& vec) {
	int max = *std::max_element(vec.begin(), vec.end());
	int min = *std::min_element(vec.begin(), vec.end());
	int range = max - min + 1;

	std::vector<int> count(range), output(vec.size());

	// Store count of each element 
	for (int i = 0; i < (int)vec.size(); ++i) {
		count[vec[i]-min]++;
	}

	// Change count[i] so that count[i] now contains actual
	// position of this element in output array
	for (int i = 1; i < (int)count.size(); ++i) {
		count[i] += count[i-1];
	}

	// keep stable
	for (int i = vec.size() - 1; i >= 0; --i) {
		output[count[vec[i]-min] - 1] = vec[i];
		--count[vec[i]-min];
	}

	for (int i = 0; i < (int)vec.size(); ++i) {
		vec[i] = output[i];
	}
}

